package 剑指offer;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author: tyy 剑指 Offer
 * 438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
 * @create: 2021-11-28 17:40
 * @description:
 **/
public class Solution34 {
    /** 滑动窗口
     * 1. 当不满足条件时，拓展右边界，当满足条件时，缩短左边界，最后得到一个解并暂存
        2.循环第一步，又得到一个解，将其与第一个解相对比，得到最优解并暂存，以此类推。
     * @param s
     * @param p
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length()<p.length()) return new ArrayList<Integer>();
        ArrayList<Integer> res = new ArrayList<>();
        int[] recordp = new int[26];
        int[] records = new int[26];
        for (int i=0;i<p.length();i++){
            recordp[p.charAt(i)-'a']++;
        }
        int cur = 0;
        for (int i=0;i<p.length();i++){
            records[s.charAt(i)-'a']++;
        }
        while (cur<=s.length()-p.length()){
            boolean flag = true;
            for (int i=0;i<26;i++){
                if (recordp[i]!=records[i]) flag=false;
            }
            if (flag) res.add(cur);
            records[s.charAt(cur)-'a']--;
            if (cur+p.length()<s.length()) records[s.charAt(cur+p.length())-'a']++;
            cur++;
        }
        return res;
    }

    /*public List<Integer> findAnagrams2(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(s.length() < p.length()) return res;
        int[] target = new int[26];
        for(char c : p.toCharArray()) target[c - 'a']++;
        int[] cur = new int[26];
        for(int i = 0; i < p.length(); ++i) cur[s.charAt(i) - 'a']++;
        if(Arrays.compare(cur,target) == 0) res.add(0);
        int l = 0,r = p.length();
        for(; r < s.length(); ++r){
            cur[s.charAt(r) -'a']++;
            cur[s.charAt(l++) - 'a']--;
            if(Arrays.compare(cur,target) == 0) res.add(l);
        }
        return res;
    }*/
    // 暴力破解 brute force
    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> list = new ArrayList<>();
        Map<Character, Integer> map = new HashMap();
        getMap(p, map);
        for (int i = 0; i < s.length(); i++) {
            char sc = s.charAt(i);
            Integer sb = map.get(sc);
            if (sb != null) {
                // 字符包含在p字符串中
                map.put(sc, -1);
                int count = 0;
                for (Integer value : map.values()) {
                    if (value == -1) {
                        count++;
                    }
                }
                if (count == p.length()) {
                    list.add(i-p.length()+1);
                }
            }else{
                map.clear();
                getMap(p, map);
            }
        }
        return list;
    }

    private void getMap(String p, Map<Character, Integer> map) {
        for (int i = 0; i < p.length(); i++) {
            char pc = p.charAt(i);
            map.put(pc, i);
        }
    }

    public static void main(String[] args) {
        Solution34 solution26 = new Solution34();
        String s = "cbaebabacd", p = "abc";
        List<Integer> anagrams = solution26.findAnagrams(s, p);
        System.out.println("anagrams = " + anagrams);

    }
}
